package map.dijkstra;

import java.util.Arrays;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n + 1][n + 1];
        for (int[] g : grid) {
            Arrays.fill(g, Integer.MAX_VALUE);
        }
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int k = scanner.nextInt();
            grid[x][y] = k;
        }
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;
        boolean[] isVisited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            int cur = 1;
            int minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (!isVisited[j] && minDist[j] < minVal){
                    minVal = minDist[j];
                    cur = j;
                }
            }
            isVisited[cur] = true;
            for (int j = 1; j <= n; j++) {
                if (!isVisited[j] && minDist[cur] + grid[cur][j] < minDist[j] && grid[cur][j] != Integer.MAX_VALUE){
                    minDist[j] = minDist[cur] + grid[cur][j];
                }
            }
        }
        if (minDist[minDist.length - 1] != Integer.MAX_VALUE){
            System.out.println(minDist[minDist.length - 1]);
        } else {
            System.out.println(-1);
        }
    }
}
